package com.platform.modules.alg.alglib.p922;

public class P922 {
    public String output = "";
    private final int M = 105;
    int i, j;
    int n; // n 表示 n 个物品
    int W; // W 表示背包的容量
    double w[] = new double[M]; // w[i] 表示第 i 个物品的重量
    double v[] = new double[M]; // v[i] 表示第 i 个物品的价值
    boolean x[] = new boolean[M]; // x[i] 表示第 i 个物品是否放入背包
    double cw;  // 当前重量
    double cp;  // 当前价值
    double bestp;  // 当前最优价值
    boolean bestx[] = new boolean[M]; // 当前最优解

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        W = Integer.parseInt(word[1]);

        for (i = 1; i <= n; i++) {
            String[] weightAndValue = line[i].split(" ");
            w[i] = Double.parseDouble(weightAndValue[0]);
            v[i] = Double.parseDouble(weightAndValue[1]);
        }
        Knapsack(W, n);
        return output;
    }

    // 计算上界（即已装入物品价值 + 剩余物品的总价值）
    double Bound(int i) {
        // 剩余物品为第 i~n 种物品
        int rp = 0;
        while (i <= n) { // 依次计算剩余物品的价值
            rp += v[i];
            i++;
        }
        return cp + rp;
    }

    // 用于搜索空间数，t 表示当前扩展结点在第t层
    void Backtrack(int t) {
        if (t > n) { // 已经到达叶子结点
            for (j = 1; j <= n; j++)
                bestx[j] = x[j];
            bestp = cp;//保存当前最优解
            return;
        }
        if (cw + w[t] <= W) { // 如果满足约束条件则搜索左子树
            x[t] = true;
            cw += w[t];
            cp += v[t];
            Backtrack(t + 1);
            cw -= w[t];
            cp -= v[t];
        }
        if (Bound(t + 1) > bestp) { // 如果满足限界条件则搜索右子树
            x[t] = false;
            Backtrack(t + 1);
        }
    }

    void Knapsack(double W, int n) {
        // 初始化当前放入背包的物品重量为 0
        cw = 0;
        // 初始化当前放入背包的物品价值为 0
        cp = 0;
        // 初始化当前最优值为0
        bestp = 0;
        // 用来统计所有物品的总重量
        double sumw = 0.0;
        // 用来统计所有物品的总价值
        double sumv = 0.0;
        for (i = 1; i <= n; i++) {
            sumv += v[i];
            sumw += w[i];
        }
        if (sumw <= W) {
            bestp = sumv;
            output = bestp + "\n";
            output += "所有的物品均放入背包。";
            return;
        }
        Backtrack(1);
        output = bestp + "\n";
        for (i = 1; i <= n; i++) { // 输出最优解
            if (bestx[i] == true)
                output += i + " ";
        }
    }
}
